﻿using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0028_SortedArrayToBST : IAlgorithm
    {
        // 108.将有序数组转换为二叉搜索树

        // 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
        // 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

        // 提示：
        //  1 <= nums.length <= 10^4
        //  -10^4 <= nums[i] <= 10^4
        //  nums 按 严格递增 顺序排列

        public void Test()
        {
            // 算法参数定义
            // 0, 1, 2, 3, 4
            var nums = new int[] { -10, -3, 0, 5, 9 };
            //var nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            // 算法执行与打印
            Console.WriteLine(SortedArrayToBST(nums));
        }

        // 算法
        // 递归，每次找中位索引，然后将左右的起点索引与终点索引传下去，直到起点索引大于终点索引
        public TreeNode SortedArrayToBST(int[] nums)
        {
            if (nums.Length <= 0)
                return null;
            var mid = nums.Length / 2;
            var result = new TreeNode(nums[mid])
            {
                left = SortedArrayToBST(nums, 0, mid - 1),
                right = SortedArrayToBST(nums, mid + 1, nums.Length - 1)
            };
            return result;
        }
        private TreeNode SortedArrayToBST(int[] nums, int s, int e)
        {
            if (s > e)
                return null;
            if (s == e)
                return new TreeNode(nums[s]);
            var mid = (s + e) / 2;
            var result = new TreeNode(nums[mid])
            {
                left = SortedArrayToBST(nums, s, mid - 1),
                right = SortedArrayToBST(nums, mid + 1, e)
            };
            return result;
        }

        //BFS，队列，同理，略
    }
}
